﻿using System;
using System.Diagnostics.Contracts;
using System.Threading;

namespace O1.Kernel.Storage
{
    [ContractVerification(true)]
    public class BlockArray<T>
    {
        public const int BlockSize = 524288;

        internal const int BlockSizeLog2 = 19;

        private T[][] storage;

        private long length;

        public BlockArray(long initialCapacity)
        {
            Contract.Requires<ArgumentOutOfRangeException>(initialCapacity > -1);
            Contract.Ensures(this.storage != null);
            Contract.Ensures(this.storage.Length > 0);

            this.length = initialCapacity;
            initialCapacity = Math.Max(1, initialCapacity);
            int blocks = unchecked((int)(initialCapacity / BlockSize));
            if (blocks * BlockSize <= initialCapacity)
            {
                blocks += 1;
            }

            var s = new T[blocks][];
            for (int i = 0; i < s.Length; i++)
            {
                s[i] = new T[BlockSize];
            }

            Contract.Assert(blocks == s.Length);
            this.storage = s;
        }

        public long Length
        {
            get
            {
                return this.length;
            }
        }

        public long Capacity
        {
            get
            {
                return this.storage.Length * BlockSize;
            }
        }

        [ContractVerification(false)]
        public T this[long index]
        {
            get
            {
                return this.storage[(int)(index >> BlockSizeLog2)][(int)(index & (BlockSize - 1))];
            }

            set
            {
                this.storage[(int)(index >> BlockSizeLog2)][(int)(index & (BlockSize - 1))] = value;
            }
        }

        public void ExpandToIndex(long index)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index > 0, "Expansion to 0 doesn't make sense.");
            Contract.Ensures(this.Capacity > index);

            lock (this.storage)
            {
                this.SynchronizedExpand(index + 1);
            }
        }

        public int Segment(long index, out T[] value)
        {
            Contract.Requires<ArgumentOutOfRangeException>(index > 0, "Expansion to 0 doesn't make sense.");
            Contract.Requires<InvalidOperationException>(this.Capacity > index, "The available capacity must exceed the index for a segment to exist. Ensure the block array is expanded first.");

            // ArgumentOutOfRange is OK for usage error here:
            Contract.Assume((int)(index >> BlockSizeLog2) < this.storage.Length);
            value = this.storage[(int)(index >> BlockSizeLog2)];
            return (int)(index & (BlockSize - 1));
        }

        private void SynchronizedExpand(long newSize)
        {
            Contract.Requires(newSize > 0);
            Contract.Ensures(this.storage != null);
            Contract.Ensures(this.Capacity > newSize);
            Contract.Ensures(this.Capacity > this.length);
            Contract.Ensures(this.storage != null);
            Contract.Ensures(this.storage.Length > 0);

            if (newSize < this.length)
            {
                Contract.Assert(this.Capacity > newSize);
                return;
            }

            this.length = newSize;
            if (newSize < this.Capacity)
            {
                Contract.Assert(this.Capacity > newSize);
                return;
            }

            var blockCount = ((int)(newSize - this.Capacity) / BlockSize) + 1;
            var expanded = new T[this.storage.Length + blockCount][];
            Contract.Assert(expanded.Length > this.storage.Length);

            if (this.storage != null)
            {
                Array.Copy(this.storage, expanded, this.storage.Length);
                for (var i = this.storage.Length; i < expanded.Length; i++)
                {
                    expanded[i] = new T[BlockSize];
                }
            }
            else
            {
                for (var i = 0; i < expanded.Length; i++)
                {
                    expanded[i] = new T[BlockSize];
                }
            }

            this.length = newSize;
            this.storage = expanded;

            Contract.Assert(this.Capacity > this.length);
        }

        [ContractInvariantMethod]
        private void ObjectInvariant()
        {
            Contract.Invariant(this.storage != null);
            Contract.Invariant(this.storage.Length > 0);
            Contract.Invariant(this.Capacity > this.length);
        }
    }
}